package thired.algorithm;



//01字符串，必须修改k次 修改后两个相邻且相同的字符串可消去，求最小长度
public class ZeroOneMinLenth {
    //优化可加map
    public static int min1(String s,int k){
        if(s == null || s.length() == 0){
            return 0;
        }
        char[] str = s.toCharArray();

        return process(str,0,k);
    }
    public static int process(char[] str,int index,int k){
        if(index == str.length){
            if(k == 0){
                int length = str.length;
                for (int i = 1; i < str.length; i++) {
                    if(str[i] == str[i - 1]){
                        length -= 2;
                        i ++;
                    }
                }
                return length;
            }else{
                return Integer.MAX_VALUE;
            }
        }
        else if(k == 0){
            return process(str,index + 1,0);
            }
        else{
            str[index] =  str[index] == '1' ? '0' : '1';
            int p = process(str,index + 1,k--);
            str[index] =  str[index] == '1' ? '0' : '1';
            int p1 = process(str,index + 1,k);
            return Math.min(p,p1);
        }
    }



    public static void main(String[] args) {
        String s1 = "101";
        String s2 = "00";
        String s3 = "01001001";
       System.out.println(min1(s1,1) );
        System.out.println(min1(s2,1) );
        System.out.println(min1(s3,3) );
    }
}
